\documentclass[10pt,pdf,hyperref={unicode}]{beamer}
\usepackage[T2A]{fontenc}       %поддержка кириллицы
%\usepackage[koi8-r]{inputenc}   %пока бибтех не дружит до конца с юникодом
\usepackage[utf8]{inputenc}
\usepackage[russian, english]{babel}     %определение языков в документе
\usepackage{amssymb,amsmath}    %математика
\usepackage{cmap}

\graphicspath{{./img/}}

% Тема презентации
\usetheme[numbers, totalnumbers, minimal, nologo]{Statmod}

%%%%%%%%%%%%%%%%%%%
%% Выбор шрифтов %%
\usefonttheme[onlylarge]{structurebold}

% Привычный шрифт для математических формул
\usefonttheme[onlymath]{serif}

% Более крупный шрифт для подзаголовков титульного листа
\setbeamerfont{institute}{size=\normalsize}
%%%%%%%%%%%%%%%%%%%

% Если используется последовательное появление пунктов списков на
% слайде (не злоупотребляйте в слайдах для защиты дипломной работы),
% чтобы еще непоявившиеся пункты были все-таки немножко видны.
\setbeamercovered{transparent}

%%%%%%%%%%%%%%%%%%
%%% Сокращения %%%
% Синий цвет выделения
\setbeamercolor{color1}{bg=blue!60!black,fg=white}
%%%%%%%%%%%%%%%%%%

\title[Обработка графа де Брюина]{Разработка алгоритмов обработки графа де Брюина в задаче геномного ассемблирования}
\author{Нурк Сергей Юрьевич, 545 гр.}
\institute{Кафедра системного программирования \\
    \vspace{0.7cm}
    Научный руководитель: Н.И. Вяххи \\
    \vspace{0.7cm}
    Рецензент: М.А. Алексеев \\
    \vspace{0.7cm}
}
\date{
    Мат-Мех СПбГУ\\
    1 июня 2011г.
}

\begin{document}
\begin{frame}
  % создаём титульный лист
  \maketitle
\end{frame}

\begin{frame}
\frametitle{Геном и секвенирование}
\begin{columns}
\column{0.5\textwidth}
\begin{itemize}
%\item Геном --- полная наследственная информация об организме
\item Геном закодирован в ДНК. Алфавит из 4 букв (A,T,G,C).
\item \textit{E.coli} --- $4.5$ млн. букв, человек --- $3.2$ млрд. букв.
\item Секвенирование --- процесс определения генома.
\item Результат --- короткие парные фрагменты ($100-200$ нуклеотидов).
\item Ассемблинг --- восстановление исходной последовательности% из фрагментов
\end{itemize}

\column{0.5\textwidth}
\includegraphics[width=\columnwidth]{sequencing}    	
\end{columns}
\end{frame}

\begin{frame}
\frametitle{Граф де Брюина}
\begin{block}{Определение}
Для фиксированного $k$, алфавита $M$ и множества строк $S \subset M^k$

$G_k(S)=<V,E>$, где
\begin{itemize}
\item $V = \{v \in M^{k-1} | \exists s \in S: v=start(s) \vee v=end(s)\}$
\item $E = \{(v_1 \rightarrow v_2)| \exists s \in S: v_1 = start(s) \wedge v_2 = end(s)\}$
\end{itemize}

\end{block}

\begin{block}{Сжатый граф де Брюина}
Получается заменой каждого неразветвленного участка одним ребром. На ребрах оказываются последовательности произвольной длины.%не короче $k$
\end{block}

\begin{alertblock}{}
Геном соответствует некоторому пути в графе.
\end{alertblock}

\end{frame}

\begin{frame}
\frametitle{Дополнительные свойства графа} %не все их поддерживают
\begin{columns}
\column{0.5\textwidth}
\begin{itemize}
\item Сопряженная структура
\item<2-> Покрытие ребер
\item<3-> Межреберные расстояния
\end{itemize}
\column{0.5\textwidth}
\only<1> {
	\includegraphics[width=0.5\columnwidth]{conjugate}  
}
\only<2> {
	\includegraphics[width=0.6\columnwidth]{coverage}  
}
\only<3> {
	\includegraphics[width=0.6\columnwidth]{pair_info}  
}
\end{columns}
\end{frame}

\begin{frame}
\frametitle{Упрощение графа}
  \begin{columns}
    \column{0.5\textwidth}
	Граф, по фрагментам
	\includegraphics[width=\columnwidth]{de_bruijn} 
    \column{0.5\textwidth}
    \only<2>{
	Упрощенный граф
	\includegraphics[width=\columnwidth]{approx}    	
	}
  \end{columns}
  \vspace{0.5cm}
\end{frame}	

\begin{frame}
\frametitle{Основные цели работы}
\begin{block}{}
\begin{itemize}
\item Спроектировать архитектуру для удобной работы с графом.
\item Разработать алгоритмы устранения ошибочных участков графа.
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Особенности реализованной архитектуры}
\begin{itemize}
\item Введены операции преобразования графа, учитывающие сопряженную структуру.%и сообщают что-то кому-то... иначе не ясно, почему удобно новый тип информации добавлять...

%\item На изменение графа может ``реагировать'' любая структура.
%\item Концепция ``событий''.%стандартная идея, паттерн проектирования, которая в этой задаче оказалась незаменимой

\item Разработаны методы пересчета покрытия и межреберных расстояний в соответствии с семантикой операций преобразования.

%\item За счет корректного состояния дополнительной информации, ее можно использовать
\item Постоянно поддерживается корректность дополнительной информации.

\item Поддержание корректности ``прозрачно'' для алгоритмов обработки.% использующих операции преобразования

\item \textbf{Итог:} просто добавлять новые типы информации, просто реализовывать алгоритмы обработки. %просто добавлять еще что-то (например, потом упомянуть про smart iterators); при написании алгоритмов используешь примитивы, не заботясь о поддержании информации (разделение логики)
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Алгоритм устранения ``пузырей''}
\begin{columns}
\column{0.5\textwidth}

\begin{itemize}
\item<2-> Для каждого достаточно короткого ребра $e$
\item<3-> Если есть альтернативный путь, от начала к концу, то:
\item<4-> Если для него выполняются некоторые условия, то:
\item<5-> Удалим $e$, ``спроектировав'' на альтернативный путь.%можем получить новый пузырь
\item<6-> Сожмем окрестности концов и включим новые ребра в обход.
\end{itemize}

\column{0.5\textwidth}
\only<1> {
	\includegraphics[width=\columnwidth]{bulge_ex_1}  
}
\only<2> {
	\includegraphics[width=\columnwidth]{bulge_ex_2}  
}
\only<3,4> {
	\includegraphics[width=\columnwidth]{bulge_ex_3}  
}
\only<5> {
	\includegraphics[width=\columnwidth]{bulge_ex_4_new}  
}
\only<6> {
	\includegraphics[width=\columnwidth]{bulge_ex_5}  
}
\only<7> {
	\includegraphics[width=\columnwidth]{bulge_ex_6}  
}
\only<8> {
	\includegraphics[width=\columnwidth]{bulge_ex_7}  
}
\end{columns}
\end{frame}

\begin{frame}
\frametitle{Особенности алгоритмов}
\begin{itemize}
\item Возможность тонкой настройки.
\item Возможность не использовать последовательности нуклеотидов за счет использования покрытия и межреберных расстояний.
\item На реальных данных по \textit{E.coli} удалено 98\% ошибочных ребер.
\item Сложность в текущей реализации $O(|E| log|E|)$.
%\item ``Понятная'' реализация за счет хорошей архитектуры.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Итоги}
\begin{itemize}
\item Разработаны алгоритмы построения и сжатия графа де Брюина.
\item Разработаны алгоритмы устранения основных типов ошибочных участков графа.
\item Разработаны новые методы работы с покрытием и межреберными расстояниями.%поддержания и использования дополнительной информации.
\item Архитектура позволяет легко расширять функциональность и разрабатывать новые алгоритмы.
\item Библиотека реализована на C++ в рамках проекта лаборатории алгоритмической биологии СПбАУ РАН.
\end{itemize}
\end{frame}

\end{document}
